package com.LeeCode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 糜烂的橘子
 */

public class Code994 {
    public static void main(String[] args) {
//        int[][] grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};

        int[][] grid = {{1,2}};
        System.out.println(new Code994().orangesRotting(grid));
    }

    public int orangesRotting(int[][] grid) {
        int row = grid.length, col = grid[0].length, res = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        int sum = 0; // 统计鲜橘子数量
        // 找到全部烂橘子
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 2) {
                    queue.add(i * col + j);
                }
                if (grid[i][j] == 1) {
                    sum++;
                }
            }
        }
        // 开始腐烂
        while (!queue.isEmpty()) {
            int size = queue.size(); // 初始腐烂橘子数量
            boolean flag = false;
            for (int i = 0; i < size; i++) {
                int pos = queue.poll();
                int r = pos / col, c = pos % col;
                if (0 <= r && r < row && 0 <= (c + 1) && (c + 1) < col && grid[r][(c + 1)] == 1) {
                    flag = true;
                    grid[r][c + 1] = 2;
                    queue.add(r * col + (c + 1));
                    sum--;
                }
                if (0 <= r && r < row && 0 <= (c - 1) && (c - 1) < col && grid[r][(c - 1)] == 1) {
                    flag = true;
                    grid[r][c - 1] = 2;
                    queue.add(r * col + (c - 1));
                    sum--;
                }
                if (0 <= (r + 1) && (r + 1) < row && 0 <= c && c < col && grid[(r + 1)][c] == 1) {
                    flag = true;
                    grid[(r + 1)][c] = 2;
                    queue.add((r + 1) * col + c);
                    sum--;
                }
                if (0 <= (r - 1) && (r - 1) < row && 0 <= c && c < col && grid[(r - 1)][c] == 1) {
                    flag = true;
                    grid[(r - 1)][c] = 2;
                    queue.add((r - 1) * col + c);
                    sum--;
                }
            }
            if (flag) { // 有新鲜橘子
                res++;
            }
        }
        if (sum > 0) { // 如果还有鲜橘子
            return -1;
        }
        return res;
    }
}
